﻿#include "stdafx.h"
#include "LongestValidParentheses.h"

using namespace std;

namespace algorithm {

    int CLongestValidParentheses::Length(string s)
    {
        int len = (int)s.length();
        int maxlen = 0;
        int left = 0;// 左括号数
        int right = 0; // 右括号数

        for (int i = 0; i < len; i++) {
            if (s[i] == '(') {
                left++;
            }
            else {
                right++;
            }
            if (right > left) {// ")"多于"("，数量置0
                right = 0;
                left = 0;
            }
            else if (right == left) { // 相等时，计算长度
                maxlen = max(maxlen, right * 2);
            }
        }

        // 反向再计算一次，处理"(" 始终多于 ")"的情况
        right = 0;
        left = 0;
        for (int i = len-1; i >= 0; i--) {
            if (s[i] == '(') {
                left++;
            }
            else {
                right++;
            }
            if (left > right) {// "("多于")"，数量置0
                right = 0;
                left = 0;
            }
            else if (right == left) { // 相等时，计算长度
                maxlen = max(maxlen, right * 2);
            }
        }

        return maxlen;
    }
}
